package BinarySearch;

import java.util.Arrays;

public class InsertIndex {
    public static void main(String[] args) {
            test();
    }
    public static int BinarySearch(int[] arr, int target) {
        int i = 0; int j = arr.length-1;
        while(i<=j){
            int m =(i + j )>>>1;
            if(target < arr[m]){
                j = m - 1;
            }
            else if(arr[m] < target){
                i = m + 1;
            }
            else if(arr[m] == target){
                return m;
            }
        }
        return -(i+1);
    }
    public static void test(){
        int[] arr = {1,5,12,16,26,35,38};
        int target = 18;
        int i = BinarySearch(arr,target);
        System.out.println(i);
        if(i<0){
            int inserIndex =Math.abs(i+1);
            int[] b =new int[arr.length+1];
            System.arraycopy(arr,0,b,0,inserIndex);
            b[inserIndex] = target;
            System.arraycopy(arr,inserIndex,b,inserIndex+1,arr.length-inserIndex);
            System.out.println(Arrays.toString(b));
        }
    }
}
